{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Computes the [Chebyshev center](https://en.wikipedia.org/wiki/Chebyshev_center) of a polyhedron.\n",
    "The example is inspired from [here](http://web.cvxr.com/cvx/examples/cvxbook/Ch04_cvx_opt_probs/html/chebyshev_center_2D.html).\n",
    "The polyhedron is defined by the following inequalities:\n",
    "\\begin{align*}\n",
    "2x + y & \\leq 1\\\\\n",
    "2x - y & \\leq 1\\\\\n",
    "-x +2y & \\leq 1\\\\\n",
    "-x -2y & \\leq 1\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Polyhedra\n",
    "A = [ 2  1\n",
    "      2 -1\n",
    "     -1  2\n",
    "     -1 -2]\n",
    "b = ones(4)\n",
    "p = SimpleHRepresentation(A, b);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1.11797e-12, 1.11801e-12], 0.44721359550145795)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Clp\n",
    "c, r = chebyshevcenter(p, ClpSolver())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Plots.GRBackend()"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import GR\n",
    "using Plots\n",
    "gr()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"600\" height=\"400\" viewBox=\"0 0 600 400\">\n",
       "<defs>\n",
       "  <clipPath id=\"clip00\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"600\" height=\"400\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip00)\" points=\"\n",
       "0,400 600,400 600,0 0,0 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip01\">\n",
       "    <rect x=\"120\" y=\"0\" width=\"421\" height=\"400\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip00)\" points=\"\n",
       "39.3701,376.378 592.126,376.378 592.126,7.87402 39.3701,7.87402 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip02\">\n",
       "    <rect x=\"39\" y=\"7\" width=\"554\" height=\"370\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  55.0141,370.85 55.0141,13.4016 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  228.837,370.85 228.837,13.4016 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  402.659,370.85 402.659,13.4016 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  576.482,370.85 576.482,13.4016 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  47.6614,336.978 583.835,336.978 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  47.6614,192.126 583.835,192.126 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:0.5; fill:none\" stroke-dasharray=\"1, 2\" points=\"\n",
       "  47.6614,47.2738 583.835,47.2738 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  39.3701,376.378 592.126,376.378 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  55.0141,376.378 55.0141,370.85 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  228.837,376.378 228.837,370.85 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  402.659,376.378 402.659,370.85 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  576.482,376.378 576.482,370.85 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  39.3701,376.378 39.3701,7.87402 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  39.3701,336.978 47.6614,336.978 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  39.3701,192.126 47.6614,192.126 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip00)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  39.3701,47.2738 47.6614,47.2738 \n",
       "  \"/>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:middle;\" transform=\"rotate(0, 55.0141, 390.178)\" x=\"55.0141\" y=\"390.178\">-1.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:middle;\" transform=\"rotate(0, 228.837, 390.178)\" x=\"228.837\" y=\"390.178\">-0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:middle;\" transform=\"rotate(0, 402.659, 390.178)\" x=\"402.659\" y=\"390.178\">0.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:middle;\" transform=\"rotate(0, 576.482, 390.178)\" x=\"576.482\" y=\"390.178\">0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:end;\" transform=\"rotate(0, 33.3701, 341.478)\" x=\"33.3701\" y=\"341.478\">-0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:end;\" transform=\"rotate(0, 33.3701, 196.626)\" x=\"33.3701\" y=\"196.626\">0.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip00)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:12; text-anchor:end;\" transform=\"rotate(0, 33.3701, 51.7738)\" x=\"33.3701\" y=\"51.7738\">0.5</text>\n",
       "</g>\n",
       "<polygon clip-path=\"url(#clip02)\" points=\"\n",
       "55.0141,192.126 472.188,18.3034 576.482,192.126 576.482,192.126 472.188,365.949 55.0141,192.126 55.0141,192.126 \n",
       "  \" fill=\"#009af9\" fill-opacity=\"1\"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#000000; stroke-width:1; stroke-opacity:1; fill:none\" points=\"\n",
       "  55.0141,192.126 472.188,18.3034 576.482,192.126 472.188,365.949 55.0141,192.126 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip02)\" style=\"stroke:#e26f46; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  558.131,192.126 557.818,183.909 556.88,175.725 555.321,167.607 553.148,159.587 550.368,151.699 546.994,143.973 543.039,136.442 538.518,129.134 533.45,122.081 \n",
       "  527.856,115.309 521.758,108.847 515.179,102.72 508.148,96.9525 500.692,91.5687 492.842,86.5897 484.628,82.0358 476.084,77.9251 467.245,74.2743 458.145,71.098 \n",
       "  448.822,68.4091 439.313,66.2183 429.657,64.5346 419.892,63.3645 410.057,62.713 400.193,62.5826 390.338,62.9738 380.533,63.885 370.818,65.3126 361.23,67.2509 \n",
       "  351.81,69.6919 342.594,72.626 333.62,76.0413 324.924,79.924 316.54,84.2585 308.504,89.0273 300.847,94.2113 293.6,99.7895 286.792,105.74 280.45,112.037 \n",
       "  274.601,118.658 269.267,125.574 264.471,132.758 260.23,140.182 256.564,147.814 253.485,155.625 251.008,163.583 249.141,171.655 247.892,179.811 247.266,188.015 \n",
       "  247.266,196.237 247.892,204.441 249.141,212.597 251.008,220.669 253.485,228.627 256.564,236.438 260.23,244.07 264.471,251.494 269.267,258.678 274.601,265.594 \n",
       "  280.45,272.214 286.792,278.512 293.6,284.462 300.847,290.041 308.504,295.225 316.54,299.994 324.924,304.328 333.62,308.211 342.594,311.626 351.81,314.56 \n",
       "  361.23,317.001 370.818,318.939 380.533,320.367 390.338,321.278 400.193,321.669 410.057,321.539 419.892,320.887 429.657,319.717 439.313,318.034 448.822,315.843 \n",
       "  458.145,313.154 467.245,309.978 476.084,306.327 484.628,302.216 492.842,297.662 500.692,292.683 508.148,287.299 515.179,281.532 521.758,275.405 527.856,268.943 \n",
       "  533.45,262.171 538.518,255.117 543.039,247.81 546.994,240.278 550.368,232.553 553.148,224.665 555.321,216.645 556.88,208.527 557.818,200.343 558.131,192.126 \n",
       "  \n",
       "  \"/>\n",
       "<circle clip-path=\"url(#clip02)\" style=\"fill:#000000; stroke:none; fill-opacity:1\" cx=\"402.659\" cy=\"192.126\" r=\"4\"/>\n",
       "<circle clip-path=\"url(#clip02)\" style=\"fill:#3da44d; stroke:none; fill-opacity:1\" cx=\"402.659\" cy=\"192.126\" r=\"3\"/>\n",
       "</svg>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plot(polyhedron(p))\n",
    "α = linspace(0, 2π, 100)\n",
    "x = c[1] .+ radius .* cos.(α)\n",
    "y = c[2] .+ radius .* sin.(α)\n",
    "plot!(x, y, linewidth=4)\n",
    "scatter!([c[1]], [c[2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
